package Chapter1.find;

import java.util.ArrayList;
import java.util.List;

public class FindSecondLinkCmmon {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node1.next = node2;
        Node node3 = new Node(2);
        node2.next = node3;
        Node node4 = new Node(3);
        node3.next = node4;
        Node node5 = new Node(3);
        node4.next = node5;
        Node node6 = new Node(5);
        node5.next = node6;
        List<Integer> integers = find(node1, node3);
        System.out.println(integers);

    }

    static class Node {
        public int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static List<Integer> find(Node node1, Node node2) {
        List<Integer> list1 = new ArrayList<>();
        while (node1 != null) {
            list1.add(node1.value);
            node1 = node1.next;
        }
        List<Integer> list2 = new ArrayList<>();
        while (node2 != null) {
            list2.add(node2.value);
            node2 = node2.next;
        }
        int i = 0, j = 0;
        List<Integer> common = new ArrayList<>();
        while (i < list1.size() && i >= 0 && j < list2.size() && j >= 0) {
            if (list1.get(i) > list2.get(j)) {
                j++;
            } else if (list1.get(i) < list2.get(j)) {
                i++;
            } else {
                common.add(list1.get(i));
                i++;
                j++;
            }
        }
        return common;
    }

}
